package 链表;

public class No24两两交换链表中的节点 {

    /**
     * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * 示例:
     * 给定 1->2->3->4, 你应该返回 2->1->4->3.
     */

    public static ListNode swapPairs(ListNode head) {

        if(head==null)
            return null;

        ListNode listNode=new ListNode();
        listNode.next=head;
        ListNode p=listNode;//上一节点
        ListNode cur=listNode.next;

        while (cur!=null&&cur.next!=null){

            //上一节点p有了
            //第一个节点cur有了
            //第二个节点cur.next有了

            ListNode nodeTwo=cur.next;//记录Node2

            //第一个指向第三个
            cur.next=cur.next.next;
            //第0个指向第二个
            p.next=nodeTwo;
            //第二个指向第一个
            nodeTwo.next=cur;

            //完毕,维护cur+p指针
            p=cur;//p指针指向第一个指针
            cur=cur.next;//cur指针指向第一个指针的下一个
        }

        return listNode.next;
    }

    /**
     * 观摩的递归解法
     * 思路:
     * 1.父函数吃什么?(包含return什么,return上去的怎么处理?)
     * (举遍历第二步的案例)按照道理应该是吃 第三个元素,让第一个元素去吃
     * 2.怎么翻转(根据题目的自定义问题)
     * one.next=DG(two.next);
     * two.next=one;
     * return two;
     */
    public static ListNode swapPairsGood(ListNode head) {

        if(head==null||head.next==null){
            return head;
        }

        ListNode nodeOne=head;
        ListNode nodeTwo=head.next;

        nodeOne.next=swapPairsGood(nodeTwo.next);

        nodeTwo.next=nodeOne;

        return nodeTwo;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,5};
        ListNode listNode = ListNode.createListNode(arr);
        ListNode result = swapPairsGood(listNode);
        ListNode.printListNode(result);
    }

}
